/**
 * Copyright (C) 2008 Christopher Allen Ogden
 *
 *     This file is part of Odysi.
 *
 *  Odysi is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  Odysi is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Odysi.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdexcept>
#include <algorithm>
#include <boost/filesystem/fstream.hpp>
#include "std.h"
#include "map.h"
#include "tileManager.h"
#include "util.h"

using std::string;
using std::runtime_error;
using std::overflow_error;
using std::sort;
using std::ios;
using boost::filesystem::fstream;
using std::streampos;
using boost::filesystem::ifstream;

using namespace MapFileFormat;

/**
 * This is used to compare objects for sorting purposes.
 */
struct compareObjects : public std::binary_function<double, double, bool>
{
    /**
     * Compare two objects to see which should come first.
     *
     * @param a The first object to compare.
     * @param b The second object to compare.
     * @return  True if the first object should come first, false if the
     *          second object should.
     */
	bool operator() (Object *a, Object *b) {
        Location aLoc(a->getLocation());
        Location bLoc(b->getLocation());
        if (aLoc.getZ() != bLoc.getZ())
            return aLoc.getZ() < bLoc.getZ();

        if (aLoc.getY() != bLoc.getY())
            return aLoc.getY() < bLoc.getY();

        if (aLoc.getX() != bLoc.getX())
            return aLoc.getX() < bLoc.getX();

        if (aLoc.getYOff() != bLoc.getYOff())
            return aLoc.getYOff() < bLoc.getYOff();

        if (aLoc.getXOff() != bLoc.getXOff())
            return aLoc.getXOff() < bLoc.getXOff();

        return a->getID() < b->getID();
    }
};

Map::Map(const std::string &fileName):
    _blockCache(MAP_BLOCK_CACHE_SIZE),
    _objectCache(MAP_OBJECT_CACHE_SIZE),
    _lastBlock(NULL),
    _lastKey(0xFFFFFFFF)
{
    fstream mapFile(fileName.c_str(), ios::binary|ios::in);

    Header header;

    // Get the width and height.
    mapFile.read(reinterpret_cast<char *>(&header), sizeof(Header));

    _widthBlocks = header.width;
    _heightBlocks = header.height;

    _width = _widthBlocks * 8;
    _height = _heightBlocks * 8;

    _mapFile = fileName;
}
    
Map::~Map()
{
    foreach (Object *p, _dynamicObject) {
        delete p;
    }
}

void Map::addObject(Object *object, bool permanent)
{
    if (!object) return;

    if (permanent) {
        // Save the object.

        // Make sure the location is within the map.
        int x = inRange(object->getX(), getWidth());
        int y = inRange(object->getY(), getHeight());

        // Get the block location.
        unsigned int blockX = x / 8;
        unsigned int blockY = y / 8;

        // Get the inner location;
        unsigned int innerX = x % 8;
        unsigned int innerY = y % 8;

        // Get the inner index.
        unsigned int innerIndex = innerY * 8 + innerX;

        // First, find the location it should be saved to
        fstream mapFile(_mapFile.c_str(), ios::binary|ios::in|ios::out);
        mapFile.exceptions(ifstream::eofbit|ifstream::failbit|ifstream::badbit);

        streampos headerPos = _widthBlocks * _heightBlocks * sizeof(Block) + sizeof(Header) + (blockY * _widthBlocks + blockX) * sizeof(ObjectsHeader);
        streampos lastHeaderPos = _widthBlocks * _heightBlocks * sizeof(Block) + sizeof(Header) + _heightBlocks * _widthBlocks * sizeof(ObjectsHeader);

        ObjectsHeader objHeader;

        // Read the header
        mapFile.seekg(headerPos, ios::beg);
        mapFile.read(reinterpret_cast<char *>(&objHeader), sizeof(ObjectsHeader));

        // Go to the offset the header tells us
        mapFile.seekg(objHeader.offset, ios::beg);

        streampos offsetInsertion = mapFile.tellg();

        for (int i = 0; i < objHeader.numItems; i++) {
            ObjectInfo info;

            mapFile.read(reinterpret_cast<char *>(&info), sizeof(ObjectInfo));

            if ((info.y > innerY) ||
                (info.y == innerY && info.x > innerX) ||
                (info.y == innerY && info.x == innerX && info.z > object->getZ())) {
                break;
            } else {
                offsetInsertion = mapFile.tellg();
            }
        }

        // Next, move all following data
        mapFile.seekg(0, ios::end);
        streampos fileEnd = mapFile.tellg();
        if (offsetInsertion != fileEnd) {
            char *data = new char[fileEnd - offsetInsertion];
            mapFile.seekg(offsetInsertion, ios::beg);

            mapFile.read(data, fileEnd - offsetInsertion);
            mapFile.seekp(offsetInsertion + static_cast<streampos>(sizeof(ObjectInfo)), ios::beg);
            mapFile.write(data, fileEnd - offsetInsertion);

            delete []data;
        }
        
        // Insert the object
        mapFile.seekp(offsetInsertion);
        ObjectInfo info;
        info.x = innerX;
        info.y = innerY;
        info.z = object->getZ();
        info.xOffset = object->getXOffset();
        info.yOffset = object->getYOffset();
        info.red = object->getRed();
        info.green = object->getGreen();
        info.blue = object->getBlue();
        info.alpha = object->getAlpha();
        info.id = object->getTileID();
        mapFile.write(reinterpret_cast<char *>(&info), sizeof(ObjectInfo));

        // Modify current object header
        objHeader.numItems++;
        mapFile.seekp(headerPos, ios::beg);
        mapFile.write(reinterpret_cast<char *>(&objHeader), sizeof(ObjectsHeader));
        mapFile.seekg(mapFile.tellp(), ios::beg);

        // Reindex all subsequent object headers
        streampos curPos = mapFile.tellp();
        while (curPos < lastHeaderPos) {
            mapFile.seekg(curPos, ios::beg);
            mapFile.read(reinterpret_cast<char *>(&objHeader), sizeof(ObjectsHeader));
            objHeader.offset += sizeof(ObjectInfo);
            mapFile.seekp(curPos, ios::beg);
            mapFile.write(reinterpret_cast<char *>(&objHeader), sizeof(ObjectsHeader));
            curPos += sizeof(ObjectsHeader);
        }
        
        // Clear the cache
        _objectCache.clear();

        // Delete the pointer
        delete object;
    } else {
        // Make sure it doesn't already exist.
        if (!permanent && getDynamicObject(object->getID())) return;

        _dynamicObject.push_back(object);
    }
}

Object *Map::getDynamicObject(int id) const
{
    foreach (Object *p, _dynamicObject) {
        if (p->getID() == id) return p;
    }
    return NULL;
}

Map::ObjectList Map::getDynamicObjects(void) const
{
    ObjectList list;

    foreach (Object *p, _dynamicObject) {
        list.push_back(p);
    }

    return list;
}

const Map::CachedObjectList * Map::getStaticObjects(int x, int y)
{
    // Make sure the location is within the map.
    x = inRange(x, getWidth());
    y = inRange(y, getHeight());

    // Get the block location.
    unsigned int blockX = x / 8;
    unsigned int blockY = y / 8;

    // Get the inner location;
    unsigned int innerX = x % 8;
    unsigned int innerY = y % 8;

    // Get the inner index.
    unsigned int innerIndex = innerY * 8 + innerX;

    // Create a block key.
    unsigned int key = x * _width + y;

    // See if the block exists in the cache.
    if (CachedObjectList *cached = _objectCache.get(key)) {
        return cached;
    }

    // Add the data to cache.

    fstream mapFile(_mapFile.c_str(), ios::binary|ios::in);
    mapFile.seekg(_widthBlocks * _heightBlocks * sizeof(Block) + sizeof(Header) + (blockY * _widthBlocks + blockX) * sizeof(ObjectsHeader), ios::beg);
    ObjectsHeader info;
    mapFile.read(reinterpret_cast<char *>(&info), sizeof(ObjectsHeader));

    CachedObjectList *list = new CachedObjectList;

    if (info.numItems) {
        mapFile.seekg(info.offset, ios::beg);

        for (int i = 0; i < info.numItems; i++) {
            ObjectInfo objInfo;

            mapFile.read(reinterpret_cast<char *>(&objInfo), sizeof(ObjectInfo));

            if (objInfo.x == innerX && objInfo.y == innerY) {
                Object o;
                o.setX(x + blockX * 8);
                o.setY(y + blockY * 8);
                o.setZ(objInfo.z);
                o.setXOffset(objInfo.xOffset);
                o.setYOffset(objInfo.yOffset);
                o.setTileID(objInfo.id);
                o.setRed(objInfo.red);
                o.setGreen(objInfo.green);
                o.setBlue(objInfo.blue);
                o.setAlpha(objInfo.alpha);

                list->push_back(o);
            }
        }
    }
    
    _objectCache.add(key, list);

    return getStaticObjects(x, y);
}

bool Map::canWalk(int startX, int startY, int endX, int endY, int z, int h)
{
    // Check to see if they are the same tile.
    if (startX == endX && startY == endY)
        return true;

    // Check to make sure the tiles are next to each other.
    if (abs(endX - startX) > 1 || abs(endY - startY) > 1)
        return false;

    // Check outbound first.
    if (!canLeave(startX, startY, endX, endY, z, h, true))
        return false;

    // Check inbound second.
    if (!canLeave(endX, endY, startX, startY, z, h))
        return false;

    // Check intermediate tiles if needed.
    if (startX != endX && startY != endY) {
        if (!canLeave(endX, startY, endX, endY, z, h))
            return false;

        if (!canLeave(startX, endY, endX, endY, z, h))
            return false;

        if (!canLeave(endX, startY, startX, startY, z, h))
            return false;

        if (!canLeave(startX, endY, startX, endY, z, h))
            return false;
    }
    return true;
}
unsigned int Map::getBlockedHeight(int x, int y, unsigned int z, int h)
{
    // Make sure the location is within the map.
    x = inRange(x, getWidth());
    y = inRange(y, getHeight());

    // Generate the line.
    unsigned char blocked[2048];
    memset(blocked, 0, 2048);
    foreach (Object *p, _dynamicObject) {
        Location loc(p->getLocation());
        if (loc.getX() == x && loc.getY() == y && p->getWalkable() == 0) {
            for (int i = loc.getZ(); i < p->getHeight() + loc.getZ(); i++) {
                if (i >= 0 && i < 2048) blocked[i] = 1;
            }
        }
    }

    // Static objects
    const CachedObjectList *list = getStaticObjects(x, y);

    foreach (const Object &o, *list) {
        if (o.getWalkable() == 0) {
            for (int i = o.getZ(); i < o.getHeight() + o.getZ(); i++) {
                if (i >= 0 && i < 2048) blocked[i] = 1;
            }
        }
    }
    
    unsigned int start = z;
    // First check if the z to h is blocked.
    bool lower = true;
    for (int i = z; i < z + h; i++) {
        if (blocked[i]) {
            lower = false;
            break;
        }
    }

    if (!lower) {
        // If so, put on top of block.
        start += h;
        while (blocked[start]) start++;
        while (!blocked[start]) start--;
        start++;
    } else {
        // Otherwise, go down until blocked.
        while (start > 0 && !blocked[start]) start--;
        if (start > 0) start++;
    }

    return start;
}

int Map::getBitmask(int x, int y, int z, int h)
{
    x = inRange(x, getWidth());
    y = inRange(y, getHeight());

    // Start with a bitmask that has all directions set.
    int bitMask = Tile::UP | Tile::DOWN | Tile::LEFT | Tile::RIGHT;

    TileManager *tm = &TileManager::GS();

    // Remove the ones for the ground tile.
    if (z == 0) {
        bitMask &= tm->getTile(LEVEL_BASE, getID(x, y, 0))->getWalkable();
        int id = getID(x, y, 1);
        if (id) bitMask &= tm->getTile(LEVEL_BASE, id)->getWalkable();
    }

    // Remove the ones for objects.
    foreach (Object *p, _dynamicObject) {
        Location loc(p->getLocation());
        if (loc.getX() == x && loc.getY() == y) {
            int oz = loc.getZ();
            unsigned int oh = p->getHeight();
            if ((oz <= z && oh + oz >= z + h) ||
               (oz >= z && oz <= z + h) ||
               (oz + oh >= z && oz + oh <= z + h)) {
                bitMask &= p->getWalkable();
            }
        }
    }

    // Static objects
    const CachedObjectList *list = getStaticObjects(x, y);

    foreach (const Object &o, *list) {
        int oz = o.getZ();
        unsigned int oh = o.getHeight();
        if ((oz <= z && oh + oz >= z + h) ||
           (oz >= z && oz <= z + h) ||
           (oz + oh >= z && oz + oh <= z + h)) {
            bitMask &= o.getWalkable();
        }
    }

    return bitMask;
}

bool Map::canLeave(int startX, int startY, int endX, int endY, int z, int h, bool ignoreZero)
{
    // Get the bitmask.
    int bitMask = getBitmask(startX, startY, z + CLIMB_HEIGHT + 1, h);

    // If it should ignore zero, and it is zero, return true.
    if (!bitMask && ignoreZero) return true;

    // See which direction they are going, then compare to the bitmask.
    if (endX < startX && !(bitMask & Tile::LEFT)) return false;
    if (endY < startY && !(bitMask & Tile::UP)) return false;
    if (startX < endX && !(bitMask & Tile::RIGHT)) return false;
    if (startY < endY && !(bitMask & Tile::DOWN)) return false;
    return true;
}

void Map::deleteObjects(int x, int y)
{
    while (x < 0) x += getWidth();
    while (y < 0) y += getHeight();

    // Make sure the location is within the map.
    x = x % getWidth();
    y = y % getHeight();

    for (ObjectList::iterator iter = _dynamicObject.begin(); iter != _dynamicObject.end(); ) {
        Location loc((*iter)->getLocation());
        if (loc.getX() == x && loc.getY() == y) iter = _dynamicObject.erase(iter);
        else ++iter;
    }

    // Delete from file

    // TODO: static objects
}

void Map::draw(int startX, int startY, int endX, int endY, int xOffset, int yOffset)
{
    sort(_dynamicObject.begin(), _dynamicObject.end(), compareObjects());
    unsigned int width = getWidth();
    unsigned int height = getHeight();

    // Draw the base tiles.
    for (int ry = startY; ry < endY; ry++) {
        for (int rx = startX; rx < endX; rx++) {
            int x = inRange(rx, static_cast<signed int>(width));
            int y = inRange(ry, static_cast<signed int>(height));

            for (int layer = 0; layer < 2; layer++) {
                int baseID = getID(x, y, layer);
                if (baseID || !layer) {
                    int dx = (rx - startX) * TILE_SIZE;
                    int dy = (ry - startY) * TILE_SIZE;
                    TileManager::GS().drawTile(LEVEL_BASE, baseID, 0, dx + xOffset, dy + yOffset);
                }
            }
        }
    }

    std::vector<Object *> toDrawObjects;

    // Draw the objects.
    for (int ry = startY; ry < endY; ry++) {
        for (int rx = startX; rx < endX; rx++) {
            int x = inRange(rx, static_cast<signed int>(width));
            int y = inRange(ry, static_cast<signed int>(height));
            int dx = (rx - startX) * TILE_SIZE + xOffset;
            int dy = (ry - startY) * TILE_SIZE + yOffset;
            const CachedObjectList *list = getStaticObjects(x, y);

            foreach (const Object &o, *list) {
                o.draw(dx, dy);
            }

            foreach (Object *p, _dynamicObject) {
                Location loc(p->getLocation());
                if (loc.getX() == x && loc.getY() == y) {
                    toDrawObjects.push_back(p);
                    p->draw(dx, dy);
                }
            }
        }
    }

    // Draw again, translucent.
    for (int ry = startY; ry < endY; ry++) {
        for (int rx = startX; rx < endX; rx++) {
            int x = inRange(rx, static_cast<signed int>(width));
            int y = inRange(ry, static_cast<signed int>(height));
            int dx = (rx - startX) * TILE_SIZE + xOffset;
            int dy = (ry - startY) * TILE_SIZE + yOffset;

            foreach (Object *p, toDrawObjects) {
                Location loc(p->getLocation());
                if (loc.getX() == x && loc.getY() == y) {
                    p->draw(dx, dy, 0.5f);
                }
            }
        }
    }
}

unsigned int Map::getAvailableID(void) const
{
    unsigned int maxID = 0;
    foreach (Object *p, _dynamicObject) {
        if (p->getID() >= maxID) maxID = p->getID() + 1;
    }
    return maxID;
}

unsigned short Map::getID(int x, int y, int layer)
{
    // Make sure the location is within the map.
    x = inRange(x, getWidth());
    y = inRange(y, getHeight());

    // Get the block location.
    unsigned int blockX = x / 8;
    unsigned int blockY = y / 8;

    // Get the inner location;
    unsigned int innerX = x % 8;
    unsigned int innerY = y % 8;

    // Get the inner index.
    unsigned int innerIndex = innerY * 8 + innerX;

    // Create a block key.
    unsigned int key = blockY * _widthBlocks + blockX;

    // See if the block exists in the cache.
    if (key == _lastKey) {
        if (layer == 0) return _lastBlock->lower[innerIndex];
        return _lastBlock->upper[innerIndex];
    }
    if (Block *cached = _blockCache.get(key)) {
        _lastKey = key;
        _lastBlock = cached;
        if (layer == 0) return cached->lower[innerIndex];
        return cached->upper[innerIndex];
    }

    // Add the data to cache.
    Block *b = new Block;

    fstream mapFile(_mapFile.c_str(), ios::binary|ios::in);

    mapFile.seekg((blockY * _widthBlocks + blockX) * sizeof(Block) + sizeof(Header), ios::beg);
    mapFile.read(reinterpret_cast<char *>(b), sizeof(Block));

    _lastBlock = b;
    _lastKey = key;
    _blockCache.add(key, b);

    return getID(x, y, layer);
}

unsigned int Map::getHeight(void) const
{
    return _height;
}

unsigned int Map::getWidth(void) const
{
    return _width;
}

void Map::setID(int x, int y, int layer, unsigned short id)
{
    // Get the width and height of the map.
    int width = getWidth();
    int height = getHeight();

    // Make sure the location is within the map.
    x = inRange(x, width);
    y = inRange(y, height);

    // Get the block location.
    unsigned int blockX = x / 8;
    unsigned int blockY = y / 8;

    // Get the inner location;
    unsigned int innerX = x % 8;
    unsigned int innerY = y % 8;

    // Get the inner index.
    unsigned int innerIndex = innerY * 8 + innerX;

    unsigned int key = blockY * _widthBlocks + blockX;

    Block *cached = _blockCache.get(key);
    if (!cached) {
        getID(x, y, 0);
        cached = _blockCache.get(key);
    }
    if (layer == 0) cached->lower[innerIndex] = id;
    else cached->upper[innerIndex] = id;

    // Set the ID.
    
    fstream mapFile(_mapFile.c_str(), ios::out|ios::binary|ios::in);

    mapFile.seekp((blockY * _widthBlocks + blockX) * sizeof(Block) + sizeof(Header), ios::beg);

    mapFile.write(reinterpret_cast<char *>(cached), sizeof(Block));
}

void Map::tick(void) 
{
    // Loop through the objects, and tick them all.
    foreach (Object *p, _dynamicObject) {
        // Tick the object.
        p->tick();
    }
}
